﻿// 我的二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <queue>
#include <iostream>
#include <stack>
using namespace std;

template <typename T>
class BinaryTree {

    private: struct TreeNode {
        T data;             // 节点存储的数据
        TreeNode* left;     // 左子节点指针
        TreeNode* right;    // 右子节点指针

        // 节点构造函数
        TreeNode(T val) : data(val), left(nullptr), right(nullptr) {}

    };

    
    public:
        // 构造函数：初始化空树
        BinaryTree() : root(nullptr) {}

     TreeNode* root;
        /*
           * 层次插入 - 按完全二叉树的方式插入
           * 这种方法保持树的完整性，适合构建完全二叉树
           *
           * 这里先添加根节点1，在添加2时 把前面1 添加到 队列里（先进先出），在遍历队列，取出最前面的数移除，
           * 然后树左边判断，左边开始，如果为NULL,则添加数值，不为空则添加到队列。
             然后右左边判断，右边开始，如果为NULL,则添加数值，不为空则添加到队列。
           * 然后在遍历队列判断是否为空，不为空从前面遍历开始继续循环执行。执行查找到为null的地方插入值
           *
           * 就是遍历是判断左右两边有没有数据，有则添加到队列，在遍历是弹出看下一层，为null则添加node搭配这个节点
           */
        void Insert(T value) {

            if (root == nullptr) {
                root = new TreeNode(value);
                return;
            }
        
                
            queue<TreeNode*> q;
          
            q.push(root);

            while (!q.empty()) {
                TreeNode* currntNode = q.front();
                q.pop();
                
                if (currntNode->left== nullptr) {
                    currntNode->left = new TreeNode(value);
                    return;
                }
                else {
                    q.push(currntNode->left);
                }

                if (currntNode->right== nullptr) {
                    currntNode->right = new TreeNode(value);
                    return;
                }
                else {
                    q.push(currntNode->right);
                }

            }
        
        }
        bool isEmpty()const {
         
            return   root == nullptr;
        }

        int size() const {

            return  sizeCount(root);
        }

        int sizeCount(TreeNode* node) const{
            if (node == nullptr)return 0;
            return 1 + sizeCount(node->left) + sizeCount(node->right);
        }

        /**
 * 显示树的基本信息
 */
        void displayInfo() const {
            std::cout << "=== 树的基本信息 ===" << std::endl;

          std::cout << "是否为空: " << (isEmpty() ? "是" : "否") << std::endl;
             std::cout << "节点数量: " << size() << std::endl;
             /*   std::cout << "树的高度: " << height() << std::endl;
            std::cout << "根节点值: " << (root ? root->data : T()) << std::endl;*/
            std::cout << "==================" << std::endl;
        }
        /**
 * 前序遍历（递归）：根 -> 左 -> 右
 * 常用于复制树、计算前缀表达式等
 */
        void preorder() const {
            std::cout << "前序遍历(递归): ";
            preorderHelper(root);
            std::cout << std::endl;
        }
        // ========== 私有辅助函数 ==========



    /**
     * 前序遍历（非递归）：使用栈实现
     * 避免递归深度过大导致的栈溢出
     */
        void preorderIterative() const {
            std::cout << "前序遍历(非递归): ";
            if (root == nullptr) return;

            std::stack<TreeNode*> s;
            s.push(root);

            while (!s.empty()) {
                TreeNode* current = s.top();
                s.pop();
                std::cout << current->data << " ";

                // 先右后左，这样出栈时就是先左后右
                if (current->right != nullptr) {
                    s.push(current->right);
                }
                if (current->left != nullptr) {
                    s.push(current->left);
                }
            }
            std::cout << std::endl;
        }

        /**
         * 中序遍历（递归）：左 -> 根 -> 右
         * 对于二叉搜索树，中序遍历会得到有序序列
         */
        void inorder() const {
            std::cout << "中序遍历(递归): ";
            inorderHelper(root);
            std::cout << std::endl;
        }

        /**
         * 中序遍历（非递归）：使用栈实现
         */
        void inorderIterative() const {
            std::cout << "中序遍历(非递归): ";
            std::stack<TreeNode*> s;
            TreeNode* current = root;

            while (current != nullptr || !s.empty()) {
                // 一直向左走到尽头
                while (current != nullptr) {
                    s.push(current);
                    current = current->left;
                }

                // 访问节点并转向右子树
                current = s.top();
                s.pop();
                std::cout << current->data << " ";
                current = current->right;
            }
            std::cout << std::endl;
        }

        /**
         * 后序遍历（递归）：左 -> 右 -> 根
         * 常用于删除树、计算后缀表达式等
         */
        void postorder() const {
            std::cout << "后序遍历(递归): ";
            postorderHelper(root);
            std::cout << std::endl;
        }

        /**
         * 层次遍历：按层从上到下，从左到右访问
         * 使用队列实现，常用于计算树的高度、宽度等
         */
        void levelOrder() const {
            if (root == nullptr) {
                std::cout << "树为空" << std::endl;
                return;
            }

            std::cout << "层次遍历: ";
            std::queue<TreeNode*> q;
            q.push(root);

            while (!q.empty()) {
                TreeNode* current = q.front();
                q.pop();
                std::cout << current->data << " ";

                if (current->left != nullptr) {
                    q.push(current->left);
                }
                if (current->right != nullptr) {
                    q.push(current->right);
                }
            }
            std::cout << std::endl;
        }




 /**
  * 递归前序遍历辅助函数
  */
        void preorderHelper(TreeNode* node) const {
            if (node == nullptr) return;
            std::cout << node->data << " ";  // 访问根节点
            preorderHelper(node->left);      // 遍历左子树
            preorderHelper(node->right);     // 遍历右子树
        }

        /**
         * 递归中序遍历辅助函数
         */
        void inorderHelper(TreeNode* node) const {
            if (node == nullptr) return;
            inorderHelper(node->left);       // 遍历左子树
            std::cout << node->data << " ";  // 访问根节点
            inorderHelper(node->right);      // 遍历右子树
        }

        /**
         * 递归后序遍历辅助函数
         */
        void postorderHelper(TreeNode* node) const {
            if (node == nullptr) return;
            postorderHelper(node->left);     // 遍历左子树
            postorderHelper(node->right);    // 遍历右子树
            std::cout << node->data << " ";  // 访问根节点
        }
};

int main()
{
    BinaryTree<int> tree;
    tree.Insert(1);
    tree.Insert(2);
    tree.Insert(3);
    tree.Insert(4);
    tree.Insert(5);
    tree.displayInfo();

    std::cout << "\n=== 遍历演示 ===" << std::endl;
    tree.preorder();            // 前序遍历  根->左->右

    tree.preorderIterative();   // 非递归前序遍历
    tree.inorder();             // 中序遍历 左->根->右

    tree.inorderIterative();    // 非递归中序遍历
    tree.postorder();           // 后序遍历 左->右->根

    tree.levelOrder();          // 层次遍历
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
